iT邦幫忙

1

leetcode with python:36. Valid Sudoku

  • 分享至 

  • xImage
  •  

題目:

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.

Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.

給定一個9x9由"1"~"9"和"."組成的二階矩陣,驗證它是不是個數獨矩陣,"."表示空白
判斷該矩陣是否為數獨矩陣標準有幾個:
1.每行不會有重複的元素
2.每列不會有重複的元素
3.9個3x3矩陣每個都不會含有重複的元素

為此我們建立了行9個,列9個,3x3矩陣9個
共27個hash set

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row=[set() for i in range(9)]
        column=[set() for i in range(9)]
        block=[set() for i in range(9)]
        
        
        for i,m in enumerate(board):
            for j,n in enumerate(m):
                if n==".":
                    continue
                if n in row[i] or n in column[j] or  n in block[(i//3)*3+j//3]:
                
                # (i//3)*3+j//3對9個3x3矩陣做0~8的編號
                    return False
            
                row[i].add(n)
                column[j].add(n)
                block[(i//3)*3+j//3].add(n)
                
        return True

遍歷所有在該二階矩陣的元素
"."表空白所以可以直接continue跳過,不必紀錄
其他元素紀錄在其所在行(j),所在列(i),所在3x3矩陣((i//3) * 3+j//3)代表的set中
一旦發現其所在行,所在列或所在3x3矩陣代表的set
已經有記錄該元素,則代表此陣列並非數獨矩陣,回傳False
而遍歷完畢都無回傳則回傳True
最後執行時間93ms(faster than 98.06%)

那我們下題見


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言